1. 题目描述（中等难度）

[warning] 150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

2. 解法一： 栈

思路： 解决这道题，主要是知道什么是逆波兰表达式，也就是中缀表达式。

我们先看一个例子...后缀表达式3 4 + 5 × 6 -的计算

• 1.从左至右扫描，将3和4压入堆栈；
• 2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
• 3.将5入栈；
• 4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
• 5.将6入栈；
• 6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

注意： 加法和减法可以不考虑顺序问题进行操作，除法和减法，是使用次顶元素进行除或者减操作

class Solution {
    public int evalRPN(String[] tokens) {
     Deque<Integer> deque = new ArrayDeque<>();
     for(String s : tokens){
       if(s.equals("+")){
          deque.offerLast(deque.pollLast()+deque.pollLast());
       }
       else if(s.equals("*")){
           deque.offerLast(deque.pollLast()*deque.pollLast());
       }
       else if(s.equals("/")){
           int n1 = deque.pollLast();
           int n2 = deque.pollLast();
           deque.offerLast(n2/n1);
       }
       else if(s.equals("-")){
           deque.offerLast(-deque.pollLast()+deque.pollLast());
       }
       else{
           deque.offerLast(Integer.valueOf(s));
       }
     }
     return deque.pollLast();
    }
}